package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {

    // Reverses the order of the elements in the specified list
    public static void reverse(MyList list) {

        for (int i = 0; i < list.size() / 2; i++) {
            swap(list, i, list.size() - i - 1);
        }
    }

    private static void swap(MyList list, int i, int j) {
        Object temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key) {
        //Если элемент найден, то возвращается его индекс. 
        //Если не найдет, то возвращается отрицательное значение, 
        //вычисляемое по следующей формуле: 
        //(-(insertion point) - 1), 
        //где insertion point - индекс того места в массиве, 
        //где должен был бы быть указанный элемент.
        if (list instanceof MyRandomAccess) {
            return indexLikeBinarySearch(list, key);
        } else {
            return indexLikeBinarySearch(list, key);
        }
    }

    private static int getCompareResult(Object first, Object second) {
        return ((Comparable) first).compareTo((Comparable) second);
    }

    private static int indexLikeBinarySearch(MyList list, Object key) {
        int low = 0;
        int high = list.size() - 1;

        while (low <= high) {
            int medium = (low + high) / 2;
            Object mediumValue = list.get(medium);
            int compareResult = getCompareResult(mediumValue, key);
            if (compareResult < 0) {
                low = medium + 1;
            } else if (compareResult > 0) {
                high = medium - 1;
            } else {
                return medium;
            }
        }
        return -low - 1;
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key, Comparator cp) {
        if (list instanceof MyRandomAccess) {
            return indexLikeBinarySearch(list, key, cp);
        } else {
            return indexLikeBinarySearch(list, key, cp);
        }
    }

    private static int indexLikeBinarySearch(MyList list, Object key,
            Comparator cp) {
        int low = 0;
        int high = list.size() - 1;
        while (low <= high) {
            int medium = (low + high) / 2;
            Object mediumValue = list.get(medium);
            int compareResult = cp.compare(mediumValue, key);
            if (compareResult < 0) {
                low = medium + 1;
            } else if (compareResult > 0) {
                high = medium - 1;
            } else {
                return medium;
            }
        }
        return -low - 1;
    }
}
